import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description: 牛客网: BM74 数字字符串转化成IP地址
 * <a href="https://www.nowcoder.com/practice/ce73540d47374dbe85b3125f57727e1e?tpId=295&tqId=653&ru=/exam/company&qru=/ta/format-top101/question-ranking&sourceUrl=%2Fexam%2Fcompany">...</a>
 * User: DELL
 * Date: 2023-06-04
 * Time: 22:29
 */
public class Solution {
    /**
     * 解题思路: 递归+回溯
     * 因为ip地址固定为四个部分,且每个部分的值应为 0~255,且除下 0,其余的数字均不能以 0 开头.
     * 因此设计dfs的时候加上一个step表明当前已经选好了几个部分了,这样子做了之后,一方面
     * 可以控制ip中的'.',另一方面也便于我们选好递归的结束条件,即step==4&&已经选完了所有字符.
     * 之后就是利用每个部分的值应为 0~255,且除下 0,其余的数字均不能以 0 开头这些条件,判断选出
     * 的字符串是否符合要求继续向下递归即可.
     * @param s string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<>();
        StringBuffer buffer = new StringBuffer();
        dfs(res,buffer,s,0,0);
        return res;
    }

    /**
     * 递归+回溯,遍历寻找每一种可能的情况
     * @param res
     * @param buffer
     * @param s
     * @param step
     * @param index
     */
    private void dfs(ArrayList<String> res, StringBuffer buffer, String s, int step, int index) {
        if (step == 4) {
            if (index == s.length()) {
                res.add(buffer.toString());
            }
        } else {
            int max = Math.min(index+3,s.length());
            for (int i = index; i < max; i++) {
                String temp = s.substring(index,i+1);
                int num = Integer.parseInt(temp);
                if (num <= 255 && (i == index || s.charAt(index) != '0')) {
                    buffer.append(temp);
                    if (step != 3) {
                        buffer.append('.');
                    }
                    dfs(res,buffer,s,step+1,i+1);
                    //回溯
                    if (step != 3) {
                        buffer.delete(index+step,i+step+2);
                    } else {
                        buffer.delete(index+step,i+step+1);
                    }
                }
            }
        }
    }
}